package 第三周;

/*
 * @author  YxinMiracle
 * @date  2022-04-28 16:29
 * @Gitee: https://gitee.com/yxinmiracle
 */


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class 课程表 {

    public int[] outDeg;
    public List<List<Integer>> to = new ArrayList<>(); //记录图的数据
    public List<Integer> ansList = new ArrayList<>();;

    /**
     * 对于prerequisites的理解
     * [0,1], 0->1,想要学习0，需要学习1 那么学习1是不需要有条件的
     * 也就是说，只要出度为0，那么就表示可以直接进行学习
     * @param numCourses 表示一共有多少节课程
     * @param prerequisites 表示限制
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        outDeg = new int[numCourses];
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) outDeg[i] = 0; // 初始化
        for (int i = 0; i < numCourses; i++) to.add(new ArrayList<>()); // 初始化
        for (int[] prerequisite : prerequisites) {
            int x = prerequisite[0];
            int y = prerequisite[1];
            to.get(y).add(x); // 构建数据
            outDeg[x]++; // 限制条件数+1
        }
        for (int i = 0; i < numCourses; i++) {
            if (outDeg[i] == 0) queue.add(i); // 没有限制条件的课程先进行学习
        }
        // 开始进行学习
        while (!queue.isEmpty()){
            Integer learned = queue.poll(); // 将数据进行取出
            ansList.add(learned);
            List<Integer> list = to.get(learned); // 取出他接下来可以学习的课程
            for (Integer courseNUm : list) {
                outDeg[courseNUm]--;
                if (outDeg[courseNUm]==0) queue.add(courseNUm); // 如果限制条件都已经学习完，即可开始学习
            }
        }
        return ansList.size() == numCourses;
    }

    public static void main(String[] args) {
        System.out.println(new 课程表().canFinish(2,new int[][]{{1,0}}));
    }

}
